package Day29;

/**
 * ---------------------------------------------------------------------------------------------------
 * 题目：
 *      给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
 *      你需要返回能表示矩阵的 四叉树 的根结点。
 *      注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
 *      四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
 *      val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
 *      isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
 * ---------------------------------------------------------------------------------------------------
 * 示例：
 *      输入：grid = [[1,1,1,1,0,0,0,0],
 *                  [1,1,1,1,0,0,0,0],
 *                  [1,1,1,1,1,1,1,1],
 *                  [1,1,1,1,1,1,1,1],
 *                  [1,1,1,1,0,0,0,0],
 *                  [1,1,1,1,0,0,0,0],
 *                  [1,1,1,1,0,0,0,0],
 *                  [1,1,1,1,0,0,0,0]]
 *      输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
 *      解释：网格中的所有值都不相同。我们将网格划分为四个子网格。
 *          topLeft，bottomLeft 和 bottomRight 均具有相同的值。
 *          topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。
 * -------------------------------------------------------------------------------------------------
 * 方法：
 *      深度优先遍历构造四叉树
 * --------------------------------------------------------------------------------------------------
 */

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}


class Solution {
    public static void main(String[] args) {

    }
    public static Node construct(int[][] grid) {
        return dfs(grid,0,0,grid.length,grid.length);
    }
    public static Node dfs(int[][] grid,int r0,int c0,int r1,int c1){
        boolean flag = true;
        for(int i = r0;i<r1;++i){
            for(int j=c0;j<c1;++j){
                if(grid[r0][c0]!=grid[i][j]){
                    flag=false;
                    break;
                }
            }
            if(!flag){
                break;
            }
        }
        if(flag){
            return new Node(grid[r0][c0]==1,true);
        }
        Node node = new Node(
            true,
            false,
            dfs(grid, r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
            dfs(grid, r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
            dfs(grid, (r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
            dfs(grid, (r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
        );
        return node;
    }
}